
The {\it Post\underline{p}oned Conflict Resolution} is a strategy (PPCR strategy)
to apply whenever there is a shift-reduce or reduce-reduce conflict which is
unsolvable using static precedences. It delays the decision, whether to shift
or reduce and by which production to reduce, to parsing time.
Let us assume the \verb|yacc|/\verb|eyapp| \mbox{compiler \cite{Rodriguez:Leon}}
announces  the presence of
a reduce-reduce conflict.
The steps followed to solve a reduce-reduce conflict using the
PPCR strategy are:

\begin{enumerate}
\item
Identify and understand the conflict: What LR(0)-items/productions and tokens are involved?.

Tools must support that stage, as for example via  the \verb|.output| file generated by \verb|eyapp| 
using option \verb|-v| or the graphical description obtained using option \verb|-w| or 
with the help of expert systems \cite{passos,basten}.
Suppose  we identify that the participants are two LR(0)-items \mbox{$A \rightarrow \alpha_\uparrow$}
and
$B \rightarrow \beta_\uparrow$ when the lookahead token is \verb|@|.

\item The software must allow the use of symbolic labels to refer
by name to the productions involved in the conflict.
Let us assume that production $A \rightarrow \alpha$
has label \texttt{:rA} and production $B \rightarrow \beta$
has label \texttt{:rB}.
A difference with \verb|yacc| is that
in \verb|Parse::Eyapp| productions can have {\it names} and {\it labels}.
In \verb|Eyapp| names and labels can be
explicitly given using the directive \verb|%name|, using a syntax similar to this one:

\begin{eqnarray*}
\mbox{{\tt \%name :rA}}& A &\rightarrow \alpha\\
\mbox{{\tt \%name :rB}}& B &\rightarrow \beta 
\end{eqnarray*}


\item
Give a symbolic name to the conflict. In this case we choose \verb|isAorB|
as name of the conflict.

\item
\label{item:mark}
Inside the {\it body} section of the grammar, mark the points of conflict using the
new reserved word \verb|%PREC| followed by the conflict name:

\begin{eqnarray*}
\mbox{{\tt \%name :rA\ }}    A &\rightarrow \alpha &\mbox{\tt\ \%PREC IsAorB }\\
\mbox{{\tt \%name :rA\ }}    B &\rightarrow \beta  &\mbox{\tt\ \%PREC IsAorB }
\end{eqnarray*}
\item
\label{item:handler}
\label{subsection:hlppcr}
Introduce a \verb|%conflict| directive inside the {\it head} section of
the translation scheme to specify the way the conflict is solved:
\begin{center}
%\begin{tabular}{p{12cm}}
\begin{VERBATIM}[numbers=none, codes={\catcode`$=3\catcode`\_=8}]
\ldots
\textbf{%conflict conflictName nestedParser? actionName: actionName}
%% /* body */
\ldots
\end{VERBATIM}
%\end{tabular}
\end{center}
Where \verb|conflictName| is the name given to the conflict,
\verb|nestedParser| refers to the sub-grammar used for pre-parsing the incoming input
and \verb|actionName| is the name of a production involved in the conflict
or the reserved word \verb|shift|. In our example is:

\begin{center}
%\begin{tabular}{p{5.3cm}}
\begin{VERBATIM}[numbers=none, codes={\catcode`$=3\catcode`\_=8}]
                \ldots
                \textbf{%conflict AorB Is\_A? :rA : :rB}
                %% /* body */
                \ldots
\end{VERBATIM}
%\end{tabular}
\end{center}
where \verb|Is_A| is an auxilary syntactic variable.
It
represents the context-dependent
dynamic knowledge that allows us to take the right
decision.
It is translated into a call to a nested parser for \verb|Is_A|.
The language defined by \verb|Is_A|
is such that any incoming 
input belongs to the language if, and only if, 
$A \rightarrow \alpha_\uparrow$ is a suitable the handler
for the anti-derivation.

\item
The point inside the body of the grammar 
in which the nested parser for \verb|Is_A| is launched 
is marked 
using the \verb|%conflictname?| syntax:
\begin{center}
%\begin{tabular}{p{5cm}}
\begin{VERBATIM}[numbers=none,codes={\catcode`$=3\catcode`\_=8\catcode`^=7}] 
                     C: $\lambda_1$ \textbf{%AorB?} $\lambda_2$
\end{VERBATIM}
%\end{tabular}
\end{center}
The set of exploration points must hold the following covering property:
any visit to the conflictive state 
must be preceded by a visit to 
an exploration state. 


%but does not exist a derivation $\lambda_2 \derives \nu_1 B \nu_2$
\end{enumerate}

The construct is translated as follows:
The parser for
\verb|Is_A| is called each time the exploration point \verb|%AorB?| 
is reached, 
saving the result inside an attribute of the parser.
Each time the conflict state 
having items $A \rightarrow \alpha_\uparrow$ and $B \rightarrow \beta_\uparrow$
is reached, this attribute is checked 
and the corresponding parsing action is taken.

\subsection{Example: a Non LR(k) Grammar}

The following example shows a PPCR solution 
for a simple non LR(k) grammar:

\begin{tabular}{|p{5.2cm}|p{5.8cm}|}
\hline
\begin{VERBATIM}[numbers=none]
\textit{/* Original grammar */}
%%
A: B C 'd' | E C 'f' ;
B: 
 'x' 'y' 
;
E: 
 'x' 'y' 
;
C: /* empty */ | C 'c' ;
\end{VERBATIM}
&
\begin{VERBATIM}[numbers=none]
\textbf{%conflict BorE Is_B? B : E}
%%
A: B C 'd' | E C 'f' ;
B: \textbf{%name B}
   'x' 'y' \textbf{%PREC BorE}
;
E: \textbf{%name E}
   'x' 'y' \textbf{%PREC BorE}
;
C: /* empty */ | C 'c' ;
\end{VERBATIM} 
\\
\hline
\end{tabular}

\noindent where \verb|Is_B| is given by the following grammar:

\begin{center}
\begin{tabular}{|p{6.0cm}|}
\hline
\begin{VERBATIM}[numbers=none]
%%
\textbf{Is\_B}:  C 'd'               ; 
C:  /* empty */ |  C 'c' ;
%%
\end{VERBATIM} 
\\
\hline
\end{tabular}
\end{center}

When no exploration point \verb|%BorE?|- as in this example -
is specified, the exploration point is the conflict point (i.e.
the places where the \verb|%PREC| directive appears).

\subsection{Example: Insufficient Lookahead}

The following grammar illustrates a typical LALR conflict due to a 
bad grammar design. The conflict between productions \verb|ds| $\rightarrow$ \verb|D ';' ds|
and \verb|ds| $\rightarrow$ \verb|D| can be easily solved by changing the second production
to  \verb|ds| $\rightarrow$ \verb|ds ';' D|.
If, for some reason, we insist in keeping the grammar, we can 
apply the PPCR methodology:

\begin{tabular}{|p{4.7cm}|p{6cm}|}
\hline
\begin{VERBATIM}[numbers=none]
%token D S

%%
p: ds ';' ss  | ss ;
ds: D ';' ds    
  | D  
;
ss: S ';' ss  | S  ;
%% 
\end{VERBATIM}
&
\begin{VERBATIM}[numbers=none]
%token D S
\textbf{%conflict LD Is_L? L : shift}
%%
p:  ds ';' ss  | ss ; 
ds: D \textbf{%PREC LD} ';' ds    
  | \textbf{%name L} D \textbf{%PREC LD}  
;
ss: S ';' ss   | S  ; 
%%
\end{VERBATIM} 
\\
\hline
\end{tabular}

Where \verb|Is_L| is given by the grammar:
\begin{center}
\begin{tabular}{|p{6.0cm}|}
\hline
\begin{VERBATIM}[numbers=none]
%%
\textbf{Is_L}: ';' S ; 
%%
\end{VERBATIM} 
\\
\hline
\end{tabular}
\end{center}

\subsection{Example:  Extended Pascal}

The third example illustrates the technique through a problem 
that arises in the declaration of enumerated and
subrange types in the programming language Pascal. 
Here are some cases:

\begin{center}
%\begin{tabular}{p{4.7cm}}
\begin{verbatim}
                     type subrange = lo .. hi;
                     type enum = (a, b, c);
\end{verbatim}
%\end{tabular}
\end{center}

The original language standard allows only numeric literals and constant
identifiers for the subrange bounds (‘\verb|lo|’ and ‘\verb|hi|’), but Extended
Pascal (ISO/IEC 10206) and many other Pascal implementations allow
arbitrary expressions there. This gives rise to declarations like the  following: 

\begin{center}
\begin{tabular}{|p{5cm}|p{3.5cm}|}
\hline
\begin{verbatim}
type subrange = (a) .. b;
\end{verbatim}
&
\begin{verbatim}
 type enum = (a);
\end{verbatim} \\
\hline
\end{tabular}
\end{center}
The corresponding declarations look identical until the `\verb|..|' token. 
Here is a PPCR solution of a  vastly simplified subgrammar of Pascal type declarations
found \mbox{in \cite{bison}}.  


\begin{center}
\begin{tabular}{|p{12cm}|}
\hline
\begin{VERBATIM}[numbers=none]
\textbf{%conflict rORe range? ID:RANGE : ID:ENUM}
%token ID  = /(\B{}A-Za-z\BB{}\Bs{}w*)/
%token NUM = /(\Bs{}d+)/
%left   ','
%left   '-' '+'
%left   '*' '/'
%%
type_decl: 'type' ID '=' type ';'                ;
type:      \textbf{%rORe?} '(' id_list ')' | \textbf{%rORe?} range ;
\textbf{range}:     expr '..' expr                        ;
id_list: 
      \textbf{%name ID:ENUM}
      ID                     \textbf{%PREC rORe}
    | id_list ',' ID
;
expr: '(' expr ')'   |  expr '+' expr
    | expr '-' expr  |  expr '*' expr
    | expr '/' expr  |  expr ',' expr
    | \textbf{%name ID:RANGE}
      ID                     \textbf{%PREC rORe}
    | NUM
;
%%
\end{VERBATIM}
\\ \hline
\end{tabular}
\end{center}

\subsection{Parsing Inherently Ambiguous Languages}
\label{section:inherentlyambiguous}
\input{ambiguous.tex}
